import java.util.LinkedList;

public class LeetCode938 {


    //中序遍历非递归 --4ms
    public int rangeSumBST(TreeNode node, int low, int high) {
        // 中序遍历 顺序是升序的方便累加
        if (node == null) {
            return 0; // 如果当前节点为空，则返回0，表示没有值可加。
        }

        TreeNode p = node; // 使用一个指针p来遍历树中的节点。
        LinkedList<TreeNode> stack = new LinkedList<>(); // 创建一个栈用于保存遍历路径上的节点。
        int sum = 0; // 定义变量用来接收满足条件的节点值之和。

        // 开始中序遍历（左-根-右），直到所有节点都被访问或栈为空。
        while (p != null || !stack.isEmpty()) {
            // 首先尽可能地向左子树深入，并将沿途的所有节点压入栈中。
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                // 当无法再向左深入时，从栈中弹出一个节点进行处理。
                p = stack.pop();

                // 如果当前节点的值大于high，根据BST性质，右边的所有节点也都会大于high，
                // 因此可以直接跳出循环，因为后续不会再有符合范围的节点。
                if (p.val > high) {
                    break;
                }

                // 如果当前节点的值在给定范围内，则将其值加入到sum中。
                // 注意：这里我们包括了low和high这两个边界值。
                if (p.val >= low) {
                    sum += p.val;
                }

                // 接下来转向右子树继续遍历。
                p = p.right;
            }
        }

        return sum; // 返回累加的结果。
    }

    //上下限递归
    public int rangeSumBST2(TreeNode node, int low, int high) {
        if (node == null) {
            return 0;
        }
        if (node.val < low) {
            return rangeSumBST2(node.right, low, high);
        }
        //如果当前值大于目标值 还是要考虑当前节点的左子节点 是否小于目标值
        if (node.val > high) {
            return rangeSumBST2(node.left, low, high);
        }
        //在范围内
        return node.val + rangeSumBST2(node.left, low, high) + rangeSumBST2(node.right, low, high);
    }
}
